package com.gxc.integer;

import java.sql.SQLOutput;

/**
 * 3133. 数组最后一个元素的最小值

 * 给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
 *
 * 返回 nums[n - 1] 可能的 最小 值。
 */
public class MinEnd {

    public static void main(String[] args) {
        System.out.println(Integer.bitCount(7));
        System.out.println(Integer.numberOfLeadingZeros(7));
        System.out.println(Integer.bitCount(2));
        System.out.println(1 & -1);
        System.out.println(2 & -2);
        System.out.println(3 & -3);
        System.out.println(4 & -4);

        System.out.println(handle(4, 4));
    }

    public static long handle(int n, int x) {
        int bitCount = 64 - Long.numberOfLeadingZeros(n) + 64- Long.numberOfLeadingZeros(x);
        long res = x;
        long m = n - 1;
        int j = 0;
        for (int i = 0; i < bitCount; ++i) {
            // x 的第 i 个比特值是 0，即「空位」
            if (((res >> i) & 1) == 0) {
                if (((m >> j) & 1) == 1) {
                    res |= (1L << i);
                }
                j++;
            }
        }
        return res;
    }

    class Solution {
        public long minEnd(int n, int x) {
            int bitCount = 64 - Long.numberOfLeadingZeros(n) + 64- Long.numberOfLeadingZeros(x);
            long res = x;
            long m = n - 1;
            int j = 0;
            for (int i = 0; i < bitCount; ++i) {
                // x 的第 i 个比特值是 0，即「空位」
                if (((res >> i) & 1) == 0) {
                    // 空位的第 n 个值
                    if (((m >> j) & 1) == 1) {
                        res |= (1L << i);
                    }
                    j++;
                }
            }
            return res;
        }
    }

    class Solution2 {
        public long minEnd(int n, int x) {
            n--; // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
            long ans = x;
            int i = 0, j = 0;
            while ((n >> j) > 0) {
                // x 的第 i 个比特值是 0，即「空位」
                if ((ans >> i & 1) == 0) {
                    // 空位填入 n 的第 j 个比特值
                    ans |= (long) (n >> j & 1) << i;
                    j++;
                }
                i++;
            }
            return ans;
        }
    }

    /**
     * 把 x 取反，用 lowbit 枚举其中的 1，就是要填的空位。
     */
    class Solution3 {
        public long minEnd(int n, int x) {
            n--;
            long ans = x;
            int j = 0;
            for (long t = ~x, lb; (n >> j) > 0; t ^= lb) {
                //位运算 t & -t 是一种常见的用于提取整数 t 最低位非零二进制位（即最低有效位或 LSB）的操作。
                lb = t & -t;
                ans |= (long) (n >> j++ & 1) * lb;
            }
            return ans;
        }
    }



}
